package _10_binary_tree.order.depth;

import _10_binary_tree.TreeNode;
import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author: mornd
 * @dateTime: 2023/6/11 - 18:04
 * 前中后序遍历合并为一个方法
 */
public class MyTest2_3 {
    @Test
    public void test() {
        polymerizationOrder(MyTest2_2.genericTestTree());
    }

    // 聚合
    void polymerizationOrder(TreeNode root) {
        List<TreeNode> pre = new ArrayList<>();
        List<TreeNode> in = new ArrayList<>();
        List<TreeNode> post = new ArrayList<>();

        TreeNode curr = root;
        LinkedList<TreeNode> stack = new LinkedList<>();

        // 记录当前节点的右子节点
        TreeNode pop = null;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                pre.add(curr); // 前序
                curr = curr.left;
            } else {
                // 左子节点处理完毕
                TreeNode peek = stack.peek();

                if (peek.right == null) {
                    pop = stack.pop();
                    in.add(pop); // 中序
                    post.add(pop); // 后序
                } else if (peek.right == pop) {
                    pop = stack.pop();
                    post.add(pop); // 后序
                } else {
                    in.add(peek); // 中序
                    curr = peek.right;
                }
            }
        }

        System.out.println("前序：" + pre);
        System.out.println("中序：" + in);
        System.out.println("后序：" + post);
    }
}
